#include <stdlib.h>
#include <string.h>
#include "CHashTable.h"

using namespace cocos2d;

CHashTable::CHashTable(int nSize)
{
	m_nSize = nSize;
	m_pTable = (LinkedList *)malloc(sizeof(LinkedList) * m_nSize);
	memset(m_pTable, NULL, sizeof(LinkedList) * m_nSize);
	m_nEntries = 0;
}

CHashTable::~CHashTable(void)
{
	Clear();
	free(m_pTable);
}

void CHashTable::Clear(void)
{
	LinkedList pCurr, pNext;

	for (int i = 0; i < m_nSize; i++)
	{
		pCurr = m_pTable[i];
		if (pCurr == NULL) continue;
		while (pCurr)
		{
			pNext = pCurr->m_pNext;
			if(pCurr->m_bCopied)
			{
				free(pCurr->m_pKey);
				if (!pCurr->m_bObjVal) 
					free(pCurr->m_pValue);
			}
			if (pCurr->m_bObjVal)
				pCurr->m_pObject->release();
			free(pCurr);
			pCurr = pNext;
		}
		m_pTable[i] = NULL;
	}
	m_nEntries = 0;
}

int CHashTable::GetHashValue(char *pKey, int nSize)
{
	unsigned int val = 0;
	int nKeyLen = strlen(pKey);

	for (int i = 0; i < nKeyLen; i++)
	{
		val = (val << 3) + pKey[i];
	}
	return (val % nSize);
}

void CHashTable::Add(char *pKey, char *pVal, bool bCopy)
{
	if (m_nEntries * 3 >= m_nSize * 2)
		Expand();

	int nHashVal = GetHashValue(pKey, m_nSize);
	Node* pNode = CreateNode(pKey, pVal, bCopy);

	if (m_pTable[nHashVal] == NULL)
	{
		m_pTable[nHashVal] = pNode;
	}
	else
	{
		pNode->m_pNext = m_pTable[nHashVal];
		m_pTable[nHashVal] = pNode;
	}
	m_nEntries ++;
}

void CHashTable::Add(char *pKey, CCObject *pObj, bool bKeyCopy)
{
	if (m_nEntries * 3 >= m_nSize * 2)
		Expand();

	int nHashVal = GetHashValue(pKey, m_nSize);
	Node* pNode = CreateNode(pKey, pObj, bKeyCopy);

	if (m_pTable[nHashVal] == NULL)
	{
		m_pTable[nHashVal] = pNode;
	}
	else
	{
		pNode->m_pNext = m_pTable[nHashVal];
		m_pTable[nHashVal] = pNode;
	}
	m_nEntries ++;
}

Node* CHashTable::CreateNode(char *pKey, char *pVal, bool bCopy)
{
	Node* pNode = (Node *)malloc(sizeof(Node));

	if (bCopy)
	{
		int len = strlen(pKey);
		pNode->m_pKey = (char *)malloc(sizeof(char) * len + 1);
		strcpy(pNode->m_pKey, pKey);
		pNode->m_pKey[len] = 0;

		len = strlen(pVal);
		pNode->m_pValue = (char *)malloc(sizeof(char) * len + 1);
		strcpy(pNode->m_pValue, pVal);
		pNode->m_pValue[len] = 0;
	}
	else
	{
		pNode->m_pKey = pKey;
		pNode->m_pValue = pVal;
	}
	pNode->m_bObjVal = false;
	pNode->m_bCopied = bCopy;
	pNode->m_pNext = NULL;
	return pNode;
}

Node* CHashTable::CreateNode(char *pKey, CCObject *pObj, bool bKeyCopy)
{
	Node* pNode = (Node *)malloc(sizeof(Node));

	if (bKeyCopy)
	{
		int len = strlen(pKey);
		pNode->m_pKey = (char *)malloc(sizeof(char) * len + 1);
		strcpy(pNode->m_pKey, pKey);
		pNode->m_pKey[len] = 0;
	}
	else
	{
		pNode->m_pKey = pKey;
	}
	pNode->m_pObject = pObj;
	pObj->retain();
	pNode->m_bObjVal = true;
	pNode->m_bCopied = bKeyCopy;
	pNode->m_pNext = NULL;
	return pNode;
}

char* CHashTable::Get(char *pKey)
{
	int nHashVal = GetHashValue(pKey, m_nSize);
	LinkedList list = m_pTable[nHashVal];

	if (list == NULL) return NULL;
	while (list)
	{
		if (strcmp(list->m_pKey, pKey) == 0)
			return list->m_pValue;
		list = list->m_pNext;
	}
	return NULL;
}

CCObject* CHashTable::GetObj(char *pKey)
{
	int nHashVal = GetHashValue(pKey, m_nSize);
	LinkedList list = m_pTable[nHashVal];

	if (list == NULL) return NULL;
	while (list)
	{
		if (strcmp(list->m_pKey, pKey) == 0)
			return list->m_pObject;
		list = list->m_pNext;
	}
	return NULL;
}

void CHashTable::Remove(char *pKey)
{
	int nHashVal = GetHashValue(pKey, m_nSize);
	LinkedList list = m_pTable[nHashVal];
	LinkedList prev, next;

	if (list == NULL) return;
	prev = NULL;
	while (list)
	{
		if (strcmp(list->m_pKey, pKey) == 0)
		{
			next = list->m_pNext;
			break;
		}
		prev = list;
		list = list->m_pNext;
	}
	if (list == NULL) return;
	if(list->m_bCopied)
	{
		free(list->m_pKey);
		if (!list->m_bObjVal)
			free(list->m_pValue);
	}
	if (list->m_bObjVal)
		list->m_pObject->release();
	free(list);
	if (prev == NULL)
	{
		m_pTable[nHashVal] = next;
	}
	else
	{
		prev->m_pNext = next;
	}
	m_nEntries --;
}

void CHashTable::Expand(void)
{
	int oldSize = m_nSize;
	int newSize = oldSize * 2;

	if (newSize == 0) newSize = 256;
	LinkedList *pNewTable = (LinkedList *)malloc(sizeof(LinkedList) * newSize);
	memset(pNewTable, NULL, sizeof(LinkedList) * newSize);
	m_nSize = newSize;
	for (int i = 0; i < oldSize; i++)
	{
		if (m_pTable[i])
		{
			LinkedList list = m_pTable[i];
			while(list)
			{
				int nHash = GetHashValue(list->m_pKey, m_nSize);
				LinkedList next = list->m_pNext;
				if (pNewTable[nHash] == NULL)
				{
					list->m_pNext = NULL;
					pNewTable[nHash] = list;
				}
				else
				{
					list->m_pNext = pNewTable[nHash];
					pNewTable[nHash] = list;
				}
				list = next;
			}
		}
	}
	free(m_pTable);
	m_pTable = pNewTable;
}
